Exercício 1 - Centralidade

Nesse exercício iremos importar, gerar e comparar a centralidade de 2 grafos:

Um pedaço da rede do facebook, coletado dos participantes de um survey que usaram o aplicativo Social Circles no Facebook (link para o dataset).
Um grafo randômico com a mesma quantidade de nós e de arestas.



In [1]:

    
import network_analysis_utils as nau
import networkx as nx

# Available functions:
#
#  - nau.facebook_nx_graph(): Obtém o grafo Networkx do facebook
#  
#  - nau.random_nx_graph(): Obtém o grafo Networkx randômico
#  
#  - nau.write_btwns_graph(nx_graph, weight_dict, output_filename): 
#      Plota o grafo em um arquivo de acordo com o dicionário de pessos obtidos do "betwenness centrality"
#
# Obs: o prefixo 'nx' indica o uso da Networkx, a lib de grafos utilizada nesse exercício

Agora você deve escrever a sua função que computa a betweenness centrality para um grafo nx:

Dica: recomendo fortemente o uso da all_shortest_paths da Networkx

Requisito: Não vale usar a função de betweenness centrality do networkx



In [2]:

    
# ALGORITHM: Betweenness Centrality
# INPUT: G(V, E)
# OUTPUT: Dictionary(V, Weights)
#
# BEGIN
#   result <- init_empty_betweenness(V)
# 
#   FOR EACH vi, vj in V THEN
# 
#     IF vi < vj THEN
#     
#       shortest_paths <- get_shortest_paths(G, vi, vj)
#     
#       contribuition <- 1 / SIZE_OF(shortest_paths)
#
#       FOR EACH path IN shortest_paths THEN
#       
#         FOR EACH pi IN path IF pi != vi AND pi != pj
#       
#           result[pi] += contribuition
#
# RETURN result
# END

def betweenness_centrality(nx_graph):
    """ Return the weight dictionary {node: betweenness centrality} """
    
    nodes = nx_graph.nodes()
    edges = nx_graph.edges()
    btwns_dict = { node: 0.0 for node in nodes }
    
    for node in nodes:
        for other in nodes:
            if (node < other): # don't double count
                paths = [p for p in nx.all_shortest_paths(nx_graph, node, other)]
                contrib = 1.0 / len(paths)
                for path in paths:
                    for n in path:
                        if n not in [node, other]:
                            btwns_dict[n] += contrib
    
    return btwns_dict

Agora que temos nossa função de centralidade pronta, podemos obter a centralidades para os dois gráficos:



In [3]:

    
facebook_graph = nau.facebook_nx_graph()
random_graph = nau.random_nx_grap()

facebook_btwns = betweenness_centrality(facebook_graph)
random_btwns = betweenness_centrality(random_graph)

E agora geraremos os gráficos dos grafos para análise visual:



In [4]:

    
nau.write_btwns_graph(facebook_graph, facebook_btwns, 'facebook_btwns_graph.png')
nau.write_btwns_graph(random_graph, random_btwns, 'random_btwns_graph.png')

Agora abra os dois arquivos gerados: facebook_btwns_graph.png e random_btwns_graph.png e analise a distribuição da centralidade.